package 蓝桥杯;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 最短路
 *
 * @author yang
 * @date 2022/1/8
 */
public class 最短路 {

    static int N = 200010;
    static int w[] = new int[N];
    static int h[] = new int[N];
    static int e[] = new int[N];
    static int ne[] = new int[N];
    static int idx, n, m, INF = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Arrays.fill(h, -1);
        while (m-- > 0) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int l = sc.nextInt();
            add(u,v,l);
        }
        spfa();
        for (int i = 2; i <= n; i++) {
            System.out.println(dist[i]);
        }
    }

    private static void spfa() {

        Arrays.fill(dist, INF);
        dist[1] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        st[1] = true;
        while (!q.isEmpty()) {
            int t = q.poll();
            st[t] = false;
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i];
                    if (!st[j]) {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }
    }

    private static void add(int a, int b, int z) {
        e[idx] = b;
        w[idx] = z;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}
